package com.kingwood.algorithm.test200;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author 22025812
 * @Description: 5G网络建设
 * https://blog.csdn.net/qfc_128220/article/details/134844501
 * @Date: 2024/3/29 15:02
 * @Modified By：
 * @Version 1.0
 */
public class MinTree {

    static class Edge {
        int from;
        int to;
        int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static int getMinCostBykruskal(Edge[] edges, int n) {
        int minCost = 0;
        Arrays.sort(edges, (a, b) -> a.weight - b.weight);

        UnionFindSet ufs = new UnionFindSet(n + 1);

        for (Edge edge : edges) {
            if (ufs.union(edge.from, edge.to)) {
                minCost += edge.weight;
                if (ufs.count == 2) {
                    return minCost;
                }
            }

        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 基站数量
        int m = scanner.nextInt(); // 边的数量

        Edge[] edges = new Edge[m];
        for (int i = 0; i < m; i++) {
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int weight = scanner.nextInt();
            int p = scanner.nextInt();

            // 已经联通，则可以认为当前边的权重为 0
            if (p == 1) {
                weight = 0;
            }

            edges[i] = new Edge(from, to, weight);
        }

        int ans = getMinCostBykruskal(edges, n);
        System.out.println(ans);
    }
}

// 并查集
class UnionFindSet {
    int[] fa;
    int count;

    public UnionFindSet(int n) {
        fa = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }

    public int find(int x) {
        if (x != fa[x]) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    public boolean union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            fa[fx] = fy;
            count--;
            return true;
        } else {
            return false;
        }
    }

}
